The present invention relates to a method of and an apparatus for predicting, at execution of a sequence of instructions by a processor, before execution of the branch instruction whether or not a branch instruction in the instruction sequence takes a branch.
General processors today use a pipeline system to execute a sequence of instructions to increase the total throughput. However, the pipeline system alone is not sufficient. Namely, when a branch instruction exists in the instruction sequence, an instruction at a branch destination thereof is only known after the branch instruction is completely executed. This causes an idle period of time in the pipeline and its performance is deteriorated. Particularly, in recent processors of a superscalar type to simultaneously execute a large number of instructions, the performance deterioration is conspicuous. To cope with this disadvantage, at a stage to fetch a branch instruction, whether the branch is xe2x80x9ctakenxe2x80x9d or is xe2x80x9cnot takenxe2x80x9d by the branch instruction is predicted to immediately fetch an instruction subsequent to the branch instruction. Namely, when the prediction is true, the performance is not deteriorated. This technique is called branch prediction and is described in detail, for example, in xe2x80x9cComputer Architecture: A Quantitative Approach Second Editionxe2x80x9d written by David A. Patterson and John L. Hennessy and published from Morgan Kaufmann Publishers. Inc. in 1996.
According to the literature above, a branch prediction mechanism is implemented by a branch prediction buffer which is accessed by low-order bits of an address of a branch instruction. Each entry of the buffer includes a counter or the like to hold 2-bit information and is updated as shown in a state transition diagrams of FIGS. 2A and 2B according to a result of the branch instruction, i.e., xe2x80x9ctakenxe2x80x9d or xe2x80x9cnot takenxe2x80x9d. In FIGS. 2A and 2B, a one-to-one correspondence exists between states 300 to 303 and values of the counter, and letter t or n assigned to an arrow between the states represents a transition condition. In branch prediction, xe2x80x9ca branch is takenxe2x80x9d is predicted for state 300 or 301 and xe2x80x9ca branch is not takenxe2x80x9d for state 302 or 303. The prediction method using the 2-bit counter predicts xe2x80x9ctakenxe2x80x9d or xe2x80x9cnot takenxe2x80x9d with a high true prediction ratio for branch instructions for which either xe2x80x9ctakenxe2x80x9d or xe2x80x9cnot takenxe2x80x9d occurs in most cases.
To increase the true prediction ratio, there has been also employed a branch prediction method in which the 2-bit counter corresponds to each historical pattern of branch instructions, not each branch instruction. This method requires, in addition to the branch prediction list, a branch history table to keep, for each branch instruction, several branch results thereof in the past. In the branch prediction of a branch instruction, the system refers to a history pattern of the branch history table by low-order bits of an address of the branch instruction and then refers to the 2-bit counter of the branch prediction table.
In addition to the branch prediction method, there has been used a prediction method using a 2-bit counter corresponding to a pattern of a comprehensive or global history of all branch instructions.
Microprocessors described in the xe2x80x9cMicroprocessor Report Oct. 26, 1998xe2x80x9d and in xe2x80x9cThe 21264: A Superscalar Alpha Microprocessor with Out-of-Order Executionxe2x80x9d of Microprocessor Forum 97th Annual adopt these branch prediction methods. FIG. 3 shows constitution of such microprocessors. A choice prediction 404 according to a global 402 is used to select a result of prediction from a local prediction 401 using a local history 400 for each branch instruction or a result of prediction from a global prediction 403 using a global history 402.
The branch prediction method of the prior art using a 2-bit counter for each branch instruction cannot appropriately predict a pattern of a branch instruction in which the conditions xe2x80x9ctakenxe2x80x9d and xe2x80x9cnot takenxe2x80x9d alternately and consecutively appear. Namely, at least 50% of predictions are false. The prediction method using a counter for the history of each branch instruction can cope with such a branch pattern. However, to hold the history of each branch instruction and to provide an increased number of counters for the history, the constituent components of hardware are considerably increased.
It is therefore an object of the present invention to provide a branch prediction apparatus in which, while keeping the prediction performance of an imbalanced branch pattern in which either xe2x80x9ctakenxe2x80x9d or xe2x80x9cnot takenxe2x80x9d occurs in most cases and which is suitably handled by the branch prediction method of the prior art, a pattern of a branch instruction in which the conditions xe2x80x9ctakenxe2x80x9d and xe2x80x9cnot takenxe2x80x9d alternately and consecutively appear is appropriately predicted only with a few additional hardware components.
In the method of prior art to select, according to the global history, either one of two predictions including the local and global branch predictions, even when each branch instruction has a tendency towards suitability of either one of the prediction methods, the selection cannot be achieved by directly using the tendency.
Another object of the present invention is to provide a branch prediction apparatus including a branch prediction apparatus above and a global branch prediction apparatus to select a prediction method according to a tendency of each branch instruction.
To achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a branch prediction table for storing one history bit and a 2-bit counter for each branch instruction, the bit and the counter being updated according to a result of xe2x80x9cbranch takenxe2x80x9d or xe2x80x9cbranch not takenxe2x80x9d for the branch instruction; a prediction generator for outputting, when the counter has a value of 0 or 2 for a branch instruction, a value of the history bit as a result of prediction and for outputting, when the counter has a value of 1 or 3 for a branch instruction, a value obtained by reversing the history bit as a result of prediction; and a counter controller for comparing for a branch instruction a result thereof with a value of the history bit before update, for setting 0 to the counter value when the result matches the value; and for adding, when the result does not match the value and the counter value is other than 3, one to the counter value.
In order to achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a branch prediction table for storing three prediction bits for each branch instruction, a prediction generator for outputting, when the prediction bits are in one of four states thereof, xe2x80x9cbranch takenxe2x80x9d as a result of prediction and for outputting, when the prediction bits are in other one of the four states thereof, xe2x80x9cbranch not takenxe2x80x9d as a result of prediction; and a prediction bit controller for controlling the prediction bits. The prediction generator generates, when a result of a branch instruction is equal to a previous result thereof, a result of prediction equal to the current result of the branch instruction at next appearance of the branch instruction. The prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs once or consecutively three times, a result of prediction opposite to the current result of the branch instruction at next appearance of the branch instruction. The prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs successively two times, a result of prediction equal to the current result of the branch instruction at next appearance of the branch instruction.
To achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a first branch predictor in accordance with claim 1 or 2, a second branch predictor for predicting a branch instruction according to a comprehensive history of all branch instructions, a choice prediction table for keeping information to be updated according to xe2x80x9ctruexe2x80x9d or xe2x80x9cfalsexe2x80x9d of predictions by the first and second branch predictors, and a selector for selecting one of the predictions by the first and second branch predictors according to the information of the choice prediction table.
The branch prediction apparatus further includes a choice table controller for adding a value to the value of the counter when the choice prediction table keeping a counter for each branch instruction and the prediction by the first branch predictor are valid and for subtracting a value from the value of the counter when the prediction by the second branch predictor is valid.